#ifndef OCTREEQUANTIZER_H
#define OCTREEQUANTIZER_H

#include "quantizer.h"

namespace WingGif {

class Octree;
class OctreeQuantizer;

class Octree : public QObject {
  Q_OBJECT
protected:
  class OctreeNode : public QObject {
  public:
    OctreeNode(int level, int colorBits, Octree *octree);
    // Construct the node
    // level : The level in the tree = 0 - 7
    // colorBits : The number of significant color bits in the image
    // octree : The tree to which this node belongs

    void addColor(QColor pixel, int colorBits, int level, Octree *octree);
    // Add a color into the tree.
    // pixel : The color
    // colorBits : The number of significant color bits
    // level : The level in the tree
    // octree : The tree to which this node belongs

    OctreeNode *nextReducible();
    QVector<OctreeNode *> &children();

    int reduce();
    // Reduce this node by removing all of its children.
    // return : The number of leaves removed.

    void constructPalette(QVector<QColor> &palette, int &paletteIndex);
    // Traverse the tree, building up the color palette.
    // palette : The palette.
    // paletteIndex : The current palette index.

    int getPaletteIndex(QColor pixel, int level);
    // Returns the palette index for the passed color.

    void increment(QColor pixel);
    // Increment the pixel count and add to the color information.

  private:
    bool _leaf;
    // Flag indicating that this is a leaf node.

    // Number of pixels in this node.
    int _pixelCount;
    int _red;
    int _green;
    int _blue;

    int _paletteIndex;
    // The index of this node in the palette.

  private:
    OctreeNode *_nextReducible;
    QVector<OctreeNode *> _children;
  };

public:
  Octree(int maxColorBits);

  QVector<OctreeNode *> &reducibleNodes();

  void addColor(QColor pixel);
  // Add a given color value to the octree

  QVector<QColor> palletize(int colorCount);
  // Convert the nodes in the octree to a palette with a maximum of colorCount
  // colors.
  // colorCount : The maximum number of colors.
  // return : An arraylist with the palettized colors

  int getPaletteIndex(QColor pixel);
  // Get the palette index for the passed color

private:
  void reduce();
  // Reduce the depth of the tree.

protected:
  void trackPrevious(OctreeNode *node);
  // Keep track of the previous node that was quantized.
  // node : The node last quantized.

private:
  static const int mask[];
  // Mask used when getting the appropriate pixels for a given node.

  OctreeNode *_root;
  // The root of the octree.

  QVector<OctreeNode *> _reducibleNodes;
  // Returns the array of reducible nodes.

  int _maxColorBits;
  // Maximum number of significant bits in the image.

  OctreeNode *_previousNode;
  // Stores the last node quantized.

  QColor _previousColor;
  // Caches the previous color quantizeds

  int _leaves;
  // Gets/Sets the number of leaves in the tree.
};

class OctreeQuantizer : public Quantizer {
public:
  OctreeQuantizer(int maxColorBits = 8);
  ~OctreeQuantizer() override;

  void initialQuantizePixel(QColor pixel) override;
  uchar quantizePixel(QColor pixel) override;
  QVector<QColor> buildPalette() override;

private:
  Octree *_octree;
};

} // namespace WingGif

#endif // OCTREEQUANTIZER_H
